package com.hanshao.sort;
//简单排序
public class SimpleSort {

    public static void swap(int[]arr,int i,int j){
        int tmp=arr[j];
        arr[j]=arr[i];
        arr[i]=tmp;
    }
    //选择排序
    public static void selectSort(int[]arr){
        if (arr==null||arr.length<2){
            return;
        }
        //0~n-1 选择最小数放到0位置
        //1~n-1 选择最小数放到1位置
        //2~n-1 选择最小数放到2位置
        int N=arr.length;
        for(int i=0;i<N;i++){
            //0~n-1
            //1~n-1
            //i~n-1
            int minValueIndex=i;
            //选择i~n位置的最小值
            for(int j=i+1;j<N;j++){
                minValueIndex=arr[j]<arr[minValueIndex]?j:minValueIndex;
            }
            swap(arr,i,minValueIndex);

        }
    }
    //冒泡排序
    public static void bubbleSort(int[]arr){
        if (arr==null&&arr.length<2){
            return;
        }
        //0~n-1
        //0~n-2
        //0~n-3
        //0~end
        int N=arr.length;
        for (int end=N-1;end>=0;end--){
           //0~end 干一件是 从end开始，谁大谁往后
            //0-1.1-2.2-3.3-4...end-1~ end
            for (int second=1;second<=end;second++){
                if(arr[second-1]>arr[second]){
                    swap(arr,second-1,second);
                }
            }
        }
    }
    //插入排序
    public static void insertSort(int[]arr){
        if (arr==null||arr.length<2){
            return;
        }
        //0~0 完成
        //0-1 有序
        //0~2 有序
        //0~n-1
        int N=arr.length;
        for (int end=1;end<N;end++){
            int newNumIndex=end;
            while (newNumIndex-1>=0&&arr[newNumIndex-1]>arr[newNumIndex]){
                swap(arr,newNumIndex-1,newNumIndex);
                newNumIndex--;
            }
        }
    }
    public static void insertSort2(int[]arr){
        if (arr==null||arr.length<2){
            return;
        }
        //0~0 完成
        //0-1 有序
        //0~2 有序
        //0~n-1
        int N=arr.length;
        for (int end=1;end<N;end++){
            // pre 新数的前一个位置
           for(int pre=end-1;pre>=0&&arr[pre]>arr[pre+1];pre--){
               swap(arr,pre,pre+1);
           }
        }
    }

    public static void print(int [] arr){
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();

    }
    public static void main(String[] args) {
         int [] arr={2,6,7,8,9,2,4,2,1,6,8,0,4,7};
        int [] arr1={2,6,7,8,9,2,4,2,1,6,8,0,4,7};
        int [] arr2={2,6,7,8,9,2,4,2,1,6,8,0,4,7};
        int [] arr3={2,6,7,8,9,2,4,2,1,6,8,0,4,7};
         print(arr);
         selectSort(arr);
         print(arr);
         bubbleSort(arr1);
         print(arr1);
         insertSort(arr2);
         print(arr2);
        insertSort2(arr3);
        print(arr3);


    }

}
